package leetcode;

/**
 * 5. 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 * <p>
 * 输入：s = "cbbd"
 * 输出："bb"
 **/
public class LongestPalindrome {
    // 中心扩散法。使用奇偶数，类似暴力法,比暴力法好点
    public static int index, len;

    public static void main(String[] args) {
        String bbb = "bb";

        LongestPalindrome.longestPalindrome1(bbb);
    }

    /**
     * 中心扩散法
     *
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }

        for (int i = 0; i < s.length() - 1; i++) {
            process(s.toCharArray(), i, i); // 奇数
            process(s.toCharArray(), i, i + 1); // 偶数
        }
        // 左闭右合
        return s.substring(index, index + len);
    }

    public static void process(char[] arr, int left, int right) {
        if (arr[left] != arr[right]) {
            return;
        }
        // 2 0 4
        while (left > 0 && right < arr.length - 1 && arr[left - 1] == arr[right + 1]) {
            left = left - 1;
            right = right + 1;
        }

        if (right - left + 1 > len) {
            index = left;
            len = right - left + 1;
        }
    }

    /**
     * 动态规划解法 推荐
     * <p>
     * 公式：dp[left][right] = dp[left+1][right-1] && arr[left] == arr[right]
     * 边界思路：先把所有的一位枚举完；再把所有的二位枚举外；再把所有的三位枚举完
     *
     * @param s
     * @return
     */
    public static String longestPalindrome1(String s) {

        // 动态规划
        boolean[][] dp = new boolean[s.length()][s.length()];

        int maxLength = 0;
        int start = 0,end = 0;

        int length = s.length();
        char[] arr = s.toCharArray();

        // 所有长度为1的串都是回文串

        for (int i = 0; i < length; i++) {
            dp[i][i] = true;
        }

        // 先枚举子串的长度
        for (int len = 2; len <= length; len++) {

            // 枚举左边界
            for (int left = 0; left < length; left++) {

                int right = left + len - 1;
                if (right >= length) {
                    break;
                }

                if (arr[left] != arr[right]) {
                    dp[left][right] = false;
                } else {

                    if (right - left <= 2) {
                        dp[left][right] = true;
                    } else {
                        dp[left][right] = dp[left + 1][right - 1];
                    }
                }

                // 判断
                if (dp[left][right] && right - left + 1 > maxLength) {
                    maxLength = right - left + 1;
                    start = left;
                    end = right;
                }
            }
        }

        // 左闭右开
        return s.substring(start, end + 1);
    }


    /**
     * 动态规划解法
     * <p>
     * 因为字符串翻转后也是一样的，可以通过求翻转后的最长公共子串，构建一个二维数组来求最长子回文串，两次循环，时间复杂度n^2
     * 但是像abc4cba和 abc4cba都有abc，却不是回文，所以不仅要求公共子串还要判断位置一下位置，即相同的元素是否为翻转得来的 i = n - j
     * <p>
     *
     * @param s
     * @return
     */
    public static String longestPalindrome2(String s) {
        if (s.equals("")) {
            return "";
        }
        String origin = s;
        String reverse = new StringBuffer(s).reverse().toString();
        int length = s.length();
        int[][] arr = new int[length][length];
        int maxLen = 0;
        int maxEnd = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (origin.charAt(i) == reverse.charAt(j)) {
                    if (i == 0 || j == 0) {
                        arr[i][j] = 1;
                    } else {
                        arr[i][j] = arr[i - 1][j - 1] + 1;
                    }
                }
                if (arr[i][j] > maxLen) {
                    // 在这要判断一下，等于的的字符是否为翻转后的字符
                    int before = length - 1 - j;
                    if (before + arr[i][j] - 1 == i) {
                        maxLen = arr[i][j];
                        maxEnd = i;
                    }
                }
            }
        }
        return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
    }
}
